from copy import deepcopy


# Definition for a Node.
class Node:
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random


class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        return deepcopy(head)


class Solution2:
    def copyRandomList(self, head: 'Node') -> 'Node':
        now_note, mid_list, old_list = head, [], []
        while now_note:
            mid_list.append(Node(now_note.val, None, now_note.random))
            old_list.append(now_note)
            now_note = now_note.next
        mid_list.append(None)
        old_list.append(None)
        for index, note in enumerate(mid_list):
            if note:
                note.next = mid_list[index+1]
                note.random = mid_list[old_list.index(note.random)]
        return mid_list[0]


class Solution3:
    def copyRandomList(self, head: 'Node') -> 'Node':
        """这样操作有一个条件,val不能重复"""
        now_note, mid_list, hash_dic = head, [], {}
        while now_note:
            new_note = Node(now_note.val, None, now_note.random)
            mid_list.append(new_note)
            hash_dic[now_note.val] = new_note
            now_note = now_note.next
        mid_list.append(None)
        for index, note in enumerate(mid_list):
            if note:
                note.next = mid_list[index+1]
                if note.random:
                    note.random = hash_dic[note.random.val]
        return mid_list[0]
